|
In graph theory, a Trémaux tree of an undirected graph ''G'' is a spanning tree of ''G'', rooted at one of its vertices, with the property that every two adjacent vertices in ''G'' are related to each other as an ancestor and descendant in the tree. All depth-first search trees and all Hamiltonian paths are Trémaux trees. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes.〔.〕〔.〕 They have also been called normal spanning trees, especially in the context of infinite graphs.〔 In finite graphs, although depth-first search itself is inherently sequential, Trémaux trees can be constructed by a randomized parallel algorithm in the complexity class RNC. They can be used to define the tree-depth of a graph, and as part of the left-right planarity test for testing whether a graph is a planar graph. A characterization of Trémaux trees in the monadic second-order logic of graphs allows graph properties involving orientations to be recognized efficiently for graphs of bounded treewidth using Courcelle's theorem. Not every infinite graph has a Trémaux tree, and the graphs that do have them can be characterized by their forbidden minors. A Trémaux tree exists in every graph with countably many vertices, even when an infinite form of depth-first search would not succeed in exploring every vertex of the graph. In an infinite graph, a Trémaux tree must have exactly one infinite path for each end of the graph, and the existence of a Trémaux tree characterizes the graphs whose topological completions, formed by adding a point at infinity for each end, are metric spaces. ==Example== In the graph shown below, the tree with edges 1–3, 2–3, and 3–4 is a Trémaux tree when it is rooted at vertex 1 or vertex 2: every edge of the graph belongs to the tree except for the edge 1–2, which (for these choices of root) connects an ancestor-descendant pair. center However, rooting the same tree at vertex 3 or vertex 4 produces a rooted tree that is not a Trémaux tree, because with this root 1 and 2 are no longer ancestor and descendant. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Trémaux tree」の詳細全文を読む スポンサード リンク
|
